#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#include "../../common/common.h"

#define N 20

// fibnacci sequence
// num of pair: 0 1 1 2 3 5 8 13 21 34...
// month:       0 1 2 3 4 5 6 7  8  9...

int fib_recursive(int n) {
    if (n < 0) {
        return 0;
    }
    if (n < 2) {
        return n;
    }
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

int fib_recursive_tail(int n, int a, int b) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return a;
    }
    if (n == 1) {
        return b;
    }
    return fib_recursive_tail(n - 1, b, a + b);
}

int fib_iteration(int n) {
    if (n < 0) {
        return 0;
    }
    if (n < 2) {
        return n;
    }
    int a = 0, b = 1;
    int t;
    while (n--) {
        t = b;
        b = a + b;
        a = t;
    }
    return a;
}

int fib_iteration_arr(int n) {
    if (n < 0) {
        return 0;
    }
    if (n < 2) {
        return n;
    }
    int* arr = (int*)malloc((n + 1) * sizeof(int));
    arr[0] = 0;
    arr[1] = 1;
    int i;
    int ret = 0;

    for (i = 2; i <= n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }

    ret = arr[n];
    free(arr);
    return ret;
}

int fib_formula(int n) {
    if (n < 0) {
        return 0;
    }
    const double sqrt_5 = sqrt(5);

    return round(
        (pow((1 + sqrt_5) / 2, n) - pow((1 - sqrt_5) / 2, n)) / sqrt_5
    );
}

// {m * p1} * {p2 * n} => {m * n}, p1 == p2
static int matrix_multiply(int* m1[], int m, int p1, int* m2[], int p2, int n, int* result[]) {
    if (p1 != p2) {
        return -1;
    }
    // int** result = (int**)calloc(m, sizeof(int*));
    if (!result) {
        return -2;
    }

    int i, j, k;

    // 矩阵乘法
    for (i = 0; i < m; i++) {
        // result[i] = (int*)calloc(n, sizeof(int));
        // if (!result) {
        //     return -3;
        // }
        for (j = 0; j < n; j++) {
            result[i][j] = 0;
            for (k = 0; k < p1; k++) {
                result[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }

    return 0;
}


int test_matrix_multiply() {
    int base[][2] = {
        {2, 3},
        {4, 5},
    };
    int* baseMatrix[] = {
        base[0],
        base[1],
    };
    int result[][2] = {
        {3, 4},
        {5, 6},
    };

    int* resultMatrix[] = {
        result[0],
        result[1],
    };

    matrix_multiply(baseMatrix, 2, 2, resultMatrix, 2, 2, resultMatrix);

    int i, j;
    /*
        {
            [21, 26]
            [37, 46]
        }

     */
    printf("test-\n");
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            printf("%3d ", resultMatrix[i][j]);
        }
        printf("\n");
    }
    printf("test-\n");
    return 0;
}

/*
    {[Fn, Fn-1]} = {[1, 1]} * {[1, 1], [1, 0]}^(n-2)
 */
int fib_matrix(int n) {
    if (n < 0) {
        return 0;
    }

    if (n < 2) {
        return n;
    }

    int base[][2] = {
        {1, 1},
        {1, 0},
    };
    int* baseMatrix[] = {
        base[0],
        base[0],
    };
    int result[][2] = {
        {1, 0},
        {0, 1},
    };

    int* resultMatrix[] = {
        result[0],
        result[1],
    };

    int pArr[] = {1, 1};
    int* pMatrix[] = {
        pArr,
    };

    int ret = 0;
    n = n - 2;

    while (n != 0) {
        if (n & 1) { // result = result * baseMatrix
            matrix_multiply(resultMatrix, 2, 2, baseMatrix, 2, 2, resultMatrix);
        }
        // baseMatrix = baseMatrix * baseMatrix
        matrix_multiply(baseMatrix, 2, 2, baseMatrix, 2, 2, baseMatrix);
        n >>= 1;
    }
    matrix_multiply(pMatrix, 1, 2, resultMatrix, 2, 2, pMatrix);

    ret = pMatrix[0][0]; // Fn
    return ret;
}

int test1() {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d  ", fib_recursive(i));
    }
    printf("\n");
    return 0;
}

int test2() {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d  ", fib_iteration_arr(i));
    }
    printf("\n");
    return 0;
}

int test3() {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d  ", fib_iteration(i));
    }
    printf("\n");
    return 0;
}

int test4() {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d  ", fib_recursive_tail(i, 0, 1));
    }
    printf("\n");
    return 0;
}

int test5() {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d  ", fib_formula(i));
    }
    printf("\n");
    return 0;
}

int test6() {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d  ", fib_matrix(i));
    }
    printf("\n");
    return 0;
}

int main(int argc, char const *argv[])
{
    double costTime = 0;
    costTime = calcCostTime(test1);
    printf("usedTime(s): %f\n", costTime);

    costTime = calcCostTime(test2);
    printf("usedTime(s): %f\n", costTime);

    costTime = calcCostTime(test3);
    printf("usedTime(s): %f\n", costTime);

    costTime = calcCostTime(test4);
    printf("usedTime(s): %f\n", costTime);

    costTime = calcCostTime(test5);
    printf("usedTime(s): %f\n", costTime);

    costTime = calcCostTime(test6);
    printf("usedTime(s): %f\n", costTime);

    test_matrix_multiply();
    return 0;
}
